import java.util.*;

public class Sorting{
	ArrayList<Tuple> inOut;
        // the diffrent types of sorting implemented
        public boolean asc = false;
        public boolean desc = false;
        public boolean same = false;
        public boolean reversed = false;
        public boolean mirror = false;
        public boolean shifted = false;
        public boolean mountain = false;
        public boolean valley = false;
        public boolean evenThenOdd = false;
        public boolean oddThenEven = false;
        public boolean grouped = false;
        ArrayList<Integer> groupedBy;

	
	public Sorting(ArrayList<Tuple> inOut){
		this.inOut=inOut;
	}

        public void findSorting(){
            sameInOut();
            reversedInOut();
            easySort();
            mirrorOut();
            shiftedOut();
            mountainOut();
            valleyOut();
            oddThenEvenOut();
            gropedOut();
        }
        private void sameInOut(){
            int a = inOut.size();
            boolean temp = true;
            for(int i = 0; i < a; i++){
                if(!inOut.get(i).get(1).equals(inOut.get(i).get(2))){
                    temp = false;
                    break;
                }
            }

            same = temp;
        }

        private void reversedInOut(){
            int a = inOut.size();
            boolean temp = true;
            for(int i = 0; i < a; i++){
                int b = inOut.get(i).get(1).size()-1;
                for(int j = 0; j <= b; j++){
                    if(inOut.get(i).get(1).get(j) != inOut.get(i).get(2).get(b-j)){
                        temp = false;
                        break;
                    }
                }
            }

            reversed = temp;
        }

        //TODO: maybe make it more general or something
        private void shiftedOut(){
            int a = inOut.size();
            int nbr = -2;
            int tempNbr;

            for(int i = 0; i < a; i++){
                tempNbr = nbrShifts(inOut.get(i).get(1),inOut.get(i).get(2));
                if(tempNbr == -1){
                    shifted =false;
                    break;
                }else if(nbr == -2){    // if uninitiallized
                    nbr = tempNbr;
                }
                else if(tempNbr != nbr){
                    nbr = -1;           // if not all examples are shifted with the same nbr
                }
                if(i == a-1){     // if last example
                    shifted = true;
                }
            }
        }

        // returns number of shifts needed to make output
        // ex 123456 -> 561234 is 2 shifts
        // TODO: one input output could have more than one nbr that is correct
        private int nbrShifts(ArrayList<Integer> input, ArrayList<Integer> output){
            ArrayList<Integer> tempList = (ArrayList)input.clone();
            int a = output.size();
            int nbr=-1;
            for(int i = 0; i <= a; i++){
                if(tempList.equals(output)){
                    nbr = i;
                    break;
                }else{
                 tempList.add(tempList.get(0));
                 tempList.remove(0);
                }
            }
            return nbr;
        }

        //TODO: Diffrent types of mirror
        //ex. 123321 321123 434434 are all examples of mirror but diffrent
        private void mirrorOut(){
            int a = inOut.size();
            boolean temp = true;
            for(int i = 0; i < a; i++){
                int b = inOut.get(i).get(1).size()-1;
                for(int j = 0; j <= b; j++){
                    if(inOut.get(i).get(2).get(j) != inOut.get(i).get(2).get(b-j)){
                        temp = false;
                        break;
                    }
                }
            }

            mirror = temp;
        }

        // TODO: now it only recognizes 46753 not 35746
        private void mountainOut(){
            int size = inOut.size();

            for(int i = 0; i < size; i++){
                if(!inOut.get(i).get(2).equals(makeMountain(inOut.get(i).get(1)))){
                    mountain = false;
                }
                else if(i == size - 1){
                    mountain = true;
                }
            }
        }

        // TODO: now it only recognizes 64357 not 75346
        private void valleyOut(){
            int size = inOut.size();

            for(int i = 0; i < size; i++){
                if(!inOut.get(i).get(2).equals(makeValley(inOut.get(i).get(1)))){
                    valley = false;
                }
                else if(i == size - 1){
                    valley = true;
                }
            }
        }

        private void oddThenEvenOut(){
            int size = inOut.size();
            ArrayList<Boolean> isEvenList;
            boolean allEvenThenOdd = true;
            boolean allOddThenEven = true;
            boolean thisEvenThenOdd = true;
            boolean thisOddThenEven = true;

            for(int i = 0 ; i < size; i++){
                isEvenList = isEven(inOut.get(i).get(2));

                if(isEvenList.contains(true) && isEvenList.contains(false)){
                    if(isEvenList.lastIndexOf(true) < isEvenList.indexOf(false)){
                        thisEvenThenOdd = true;
                        thisOddThenEven = false;
                    }else if (isEvenList.lastIndexOf(false) < isEvenList.indexOf(true)){
                        thisEvenThenOdd = false;
                        thisOddThenEven = true;
                    }else{
                        thisEvenThenOdd = false;
                        thisOddThenEven = false;
                    }
                }
                else{
                    thisEvenThenOdd = true;
                    thisOddThenEven = true;
                }
                if(allEvenThenOdd != thisEvenThenOdd){
                    allEvenThenOdd = false;
                }
                if(allOddThenEven != thisOddThenEven){
                    allOddThenEven = false;
                }
            }
            oddThenEven = allOddThenEven;
            evenThenOdd = allEvenThenOdd;

        }

        private void gropedOut(){
            int size = inOut.size();
            ArrayList<Integer> possGroups = new ArrayList<Integer>();
            ArrayList<Integer> tempGroups = new ArrayList<Integer>();;
            int nbrPoss;
            boolean group = true;

            for(int i = 0; i < size; i++){
                if(i == 0)
                    possGroups = possibleGroupSizes(inOut.get(i).get(1),inOut.get(i).get(2));
                else{
                    tempGroups = possibleGroupSizes(inOut.get(i).get(1),inOut.get(i).get(2));
                    nbrPoss = possGroups.size();
                    for(int j = 0; j < nbrPoss; j++){
                        if(!tempGroups.contains(possGroups.get(j))){
                            possGroups.remove(i);
                        }
                    }
                }
                if(possGroups.isEmpty()){
                    group = false;
                    break;
                }
            }
            grouped = group;
            groupedBy = possGroups;
        }

        private ArrayList<Integer> makeMountain(ArrayList<Integer> input){
            ArrayList<Integer> tempList = (ArrayList<Integer>)input.clone();
            ArrayList<Integer> mountainList = new ArrayList<Integer>();
            int size = input.size();
            int highest;

            for(int i = 0; i < size; i++){
                highest = findHighest(tempList);
                tempList.remove(tempList.indexOf(highest));

                if(i%2 == 0){
                    mountainList.add(highest);
                }else{
                    mountainList.add(0, highest);
                }
            }



            return mountainList;
        }

        private ArrayList<Integer> makeValley(ArrayList<Integer> input){
            ArrayList<Integer> tempList = (ArrayList)input.clone();
            ArrayList<Integer> valleyList = new ArrayList<Integer>();
            int size = input.size();
            int lowest;

            for(int i = 0; i < size; i++){
                lowest = findLowest(tempList);
                tempList.remove(tempList.indexOf(lowest));

                if(i%2 == 0){
                    valleyList.add(lowest);
                }else{
                    valleyList.add(0, lowest);
                }
            }



            return valleyList;
        }

        private int findHighest(ArrayList<Integer> input){
            int size = input.size();
            int highest = Integer.MIN_VALUE;
            for(int i =0; i < size; i++){
                if(input.get(i)> highest){
                    highest = input.get(i);
                }
            }
            return highest;
        }

        private int findLowest(ArrayList<Integer> input){
            int size = input.size();
            int lowest = Integer.MAX_VALUE;
            for(int i =0; i < size; i++){
                if(input.get(i)< lowest){
                    lowest = input.get(i);
                }
            }
            return lowest;
        }

        private ArrayList<Integer> possibleGroupSizes(ArrayList<Integer> input, ArrayList<Integer> output){
            ArrayList<Integer> possibleSizes = new ArrayList<Integer>();
            ArrayList<List> inputVariants = new ArrayList<List>();
            ArrayList<List> outputVariants = new ArrayList<List>();
            int size = input.size();

            for(int i = 2; i < size; i++){
                if(size % i == 0){
                    possibleSizes.add(size / i);
                    inputVariants.add(divideToGroups(input,size / i));
                    outputVariants.add(divideToGroups(output,size / i));
                }
            }
            size = possibleSizes.size();
            for(int i = 0; i < size; i++){
                if(!groupingOK((ArrayList<List>) inputVariants.get(i), (ArrayList<List>)outputVariants.get(i))){
                    possibleSizes.remove(i);
                    inputVariants.remove(i);
                    outputVariants.remove(i);
                    size--;
                    i--;
                }
            }

            return possibleSizes;
        }

        private ArrayList<List> divideToGroups(ArrayList<Integer> input, int length){
            ArrayList<List> divided = new ArrayList<List>();
            int size = input.size();
            
            for(int i = 0 ; i < size; i += length){
                divided.add(input.subList(i, i + length));
            }

            return divided;
        }

        private boolean groupingOK(ArrayList<List> input, ArrayList<List> output){
            ArrayList<List> in = (ArrayList<List>) input.clone();
            ArrayList<List> out = (ArrayList<List>) output.clone();
            int size = in.size();

            for(int i = 0 ; i < size; i++){
                for(int j = 0 ; j < size; j++){
                    if(in.get(i).equals(out.get(j))){
                        in.remove(i);
                        out.remove(j);
                        size--;
                        i=-1;
                        j=-1;
                        break;
                    }else if(j == size-1){
                        return false;
                    }
                }
            }
            return true;
        }

        // check if Asc or desc sorting
	private void easySort(){
            ArrayList<List> allLessThanNext = new ArrayList<List>();
            boolean easySort = true;
            boolean lastRow = false;    // last row only had?
            int a = inOut.size();
            for(int i=0; i<a; i++){
                    allLessThanNext.add(allLessThanNext(inOut.get(i).get(2)));
                    if(easySort){
                        easySort = !(allLessThanNext.get(i).contains(true) && allLessThanNext.get(i).contains(false));
                        if(easySort){
                            if(i == 0){ // ugly solution for uninitialized variable
                                lastRow = (Boolean) allLessThanNext.get(0).get(1);
                            }
                            easySort = (lastRow == (Boolean) allLessThanNext.get(i).get(1));
                            lastRow = (Boolean) allLessThanNext.get(i).get(1);
                        }
                    }
            }
            if(easySort){
                asc = lastRow;
                desc = !lastRow;
            }
	}

        private ArrayList<Boolean> allLessThanNext(ArrayList<Integer> output){
            int a = output.size()-1;
            boolean temp = true;
            int j = 0;
            ArrayList<Boolean> tempList = new ArrayList<Boolean>();

            for(int i = 0; i < a; i++){
                if(output.get(i) == output.get(i+1)){
                    j++;
                }else{
                    j++;
                    temp = output.get(i) < output.get(i+1);
                    while(j>0){
                        tempList.add(temp);
                        j--;
                    }
                }
                if(i+1 == a){   // if last element
                    while(j>0){ 
                        tempList.add(temp);
                        j--;
                    }
                }
            }
            return tempList; //temp
	}

        private ArrayList<Boolean> isEven(ArrayList<Integer> output){
            int size = output.size();
            ArrayList<Boolean> isEvenList = new ArrayList<Boolean>();

            for(int i = 0; i < size ; i++){
                if(output.get(i) % 2 == 0){
                    isEvenList.add(true);
                }else{
                    isEvenList.add(false);
                }
            }

            return isEvenList;
        }
}
